package com.mlh.backtracking;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * @author 缪林辉
 * @date 2024/4/5 10:54
 * @DESCRIPTION
 */
// 给你一个字符串 s，请你将 s 分割成一些子串，
// 使每个子串都是 回文串。返回 s 所有可能的分割方案。
// 输入：s = "aab"
// 输出：[["a","a","b"],["aa","b"]]
public class 分割回文串 {
    List<List<String>>res=new ArrayList<>();
    LinkedList<String>path=new LinkedList<>();
    //自己写出
    public List<List<String>> method1(String s) {
        char[] chars = s.toCharArray();
        recursion(0,chars.length-1,chars);
        return res;
    }

    //这里依然用抽象树结构很好理解
    //但是他和之前组合的模式不一样  这里是分割问题
    //组合是选取一个数 就可以往下走
    //这里需要判断，你想往下走你必须保证你此时选择出来的子串是回文串，才能往下走
    //其次，这里树的同一层是 同一起始点i 到不同终止位置（最后是到chars的末尾位置）的子串
    //整个逻辑就是 我从i位置到某个终止位置 选出一个子串，这个子串是回文串，
    //此时就可以往下走，下一个子串的位置应该是该子串终止位置+1

    //start就是切割线
    public void recursion(int start,int end ,char[]chars){
        if(start>end){
            res.add(new ArrayList<>(path));
            return;
        }
        for (int i = start; i <=end; i++) {
            if(!method1Aux(start,i,chars)){
                continue;
            }
            //从start切割到i 形成一个子串
            path.add(new String(chars,start,i-start+1));
            //下一次从i+1处开始切割
            recursion(i+1,end,chars);
            path.removeLast();
        }
    }

    //判断字符串是否为回文串
    //这里还可以调优，利用动态规划
    public boolean method1Aux(int start,int end ,char[]chars){
        while(start<=end){
            if(chars[start++]!=chars[end--]){
                return false;
            }
        }
        return true;
    }

    // 实现优化的方式 通过dp来优化回文子串的判断
    boolean[][]is;
    int sLen;
    public List<List<String>> practice(String s) {
        sLen=s.length();
        //构造回文子串判断辅助矩阵
        is=new boolean[sLen][sLen];
        for (int i = sLen-1; i >=0; i--) {
            for (int j = i; j < sLen; j++) {
                if(j-i<2){
                    is[i][j]=s.charAt(i)==s.charAt(j);
                }else{
                    is[i][j]=s.charAt(i)==s.charAt(j)&&is[i+1][j-1];
                }
            }
        }
        recursionPractice(0,s);
        return  res;
    }

    public void recursionPractice(int start,String s){
        if(start>=sLen){
            res.add(new ArrayList<>(path));
            return;
        }
        for (int i = start; i < sLen; i++) {
            if(!is[start][i]){
                continue;
            }
            path.add(s.substring(start,i+1));
            recursionPractice(i+1,s);
            path.removeLast();
        }
    }

    public List<List<String>> practice2(String s) {
        int sLen=s.length();
        boolean[][]dp=new boolean[sLen][sLen];
        for (int i = sLen-1; i >=0; i--) {
            for (int j = i; j < sLen; j++) {
                if(j-i<2){
                    dp[i][j]=s.charAt(i)==s.charAt(j);
                }else{
                    dp[i][j]=s.charAt(i)==s.charAt(j)&&dp[i+1][j-1];
                }
            }
        }
        recursionPractice2(s,dp,0);
        return res;
    }
	public void recursionPractice2(String s,boolean[][]dp,int start){
		if(start==s.length()){
            res.add(new ArrayList<>(path));
			return;
		}
        for (int i = start; i <s.length() ; i++) {
            if(!dp[start][i]){
                continue;
            }
            path.add(s.substring(start,i+1));
            recursionPractice2(s,dp,i+1);
            path.removeLast();
        }
	}

    public static void main(String[] args) {
        分割回文串 a = new 分割回文串();
        List<List<String>> aab = a.practice2("aab");
        System.out.println(1);
    }
}
